5832. Array With Elements Not Equal to Average of Neighbors

Description

image-20210816013507734

image-20210816013517964

Solution

To generate the array in the requirement, my strategy is pickthe smallest the largest the second smallest …, because we have the largest * 2 > the sum of the smallest numbers, it should always work.

Or we can keep looping the swap the mismatched pair till we get the correct array.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<int> rearrangeArray(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int l = 0, r = nums.size()-1;
        vector<int> res;
        while(res.size() != nums.size()){
            res.push_back(nums[l++]);
            if(l < r)
                res.push_back(nums[r--]);
        }
        return res;
    }
    
};

Solution 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<int> rearrangeArray(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int l = 0, r = nums.size()-1;
        vector<int> res;
        while(res.size() != nums.size()){
            res.push_back(nums[l++]);
            if(l < r)
                res.push_back(nums[r--]);
        }
        return res;
    }
    
};